#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
    ElemType *elem; //整形指针，申请的堆空间起始地址存入elem
    int TableLen;   //存储动态数组里边元素的个数
}SSTable;

//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem= (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
//打印顺序表
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//实现二分查找
int BinarySearch(SSTable ST,ElemType key)
{
    int low=0;
    int high=ST.TableLen-1;
    int mid;
    while (low<=high)  //取等于是为了让mid即能取到low还能取到high
    {
        mid=(low+high)/2;
        if(key<ST.elem[mid])
        {
            high=mid-1;
        } else if(key>ST.elem[mid])
        {
            low=mid+1;
        } else{
            return mid;
        }
    }
    return -1;
}
//函数名中存储的是函数的入口地址，也是一个指针，是函数指针类型
//left指针和right指针是指向数组的任意两个元素
//qsort规定如果left指针指向的值大于right指针指向的值，返回正值，小于返回负值，相等返回0
int compare(const void *left,const void *right)
{
    return *(ElemType*)left-*(ElemType*)right; //*(ElemType*)left取left指向的值
    //return *(ElemType*)right-*(ElemType*)left;
}
//二分查找
int main() {
    SSTable ST;
    ST_Init(ST,10);  //随机初始10个元素
    ST_Print(ST);
    qsort(ST.elem,ST.TableLen, sizeof(ElemType),compare); //排序
    ST_Print(ST);
    ElemType key;
    printf("please input search key:\n");
    scanf("%d",&key);
    int pos=BinarySearch(ST,key);
    if(pos!=-1)
    {
        printf("find the key=%d\n",pos);
    } else{
        printf("not find\n");
    }
    return 0;
}
